package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
 **/
public class No021 {

    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了98.49%的用户
     * 内存消耗：47.8 MB, 在所有 Java 提交中击败了10.93%的用户
     */
    public int[] exchange(int[] nums) {
        int[] res = new int[nums.length];

        int left = 0;
        int right = nums.length - 1;

        for (int num : nums) {
            if (num % 2 != 0) {
                res[left++] = num;
            } else {
                res[right--] = num;
            }
        }

        return res;
    }

    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了98.49%的用户
     * 内存消耗：46 MB, 在所有 Java 提交中击败了91.12%的用户
     */
    public int[] exchange1(int[] nums) {

        int left = 0;
        int right = nums.length - 1;
        int tmp = 0;

        while (left < right) {
            if (nums[left] % 2 != 0) {
                left++;
            } else if (nums[right] % 2 == 0) {
                right--;
            } else if (nums[left] % 2 == 0 && nums[right] % 2 != 0) {
                tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            } else {
                left++;
                right--;
            }
        }

        return nums;
    }
}
